`
https://leetcode.cn/problems/super-pow/
`

const base = 1337

/**
 * @param {number} a
 * @param {number[]} b
 * @return {number}
 */
var superPow = function (a, b) {
  // https://labuladong.online/algo/frequency-interview/quick-power/
  if (b.length === 0) return 1;
  const last = b.pop();

  const part1 = mypow(a, last);
  const part2 = mypow(superPow(a, b), 10);
  // 每次乘法都要求模
  return (part1 * part2) % base;
};

function mypow(a, k) {
  if (k === 0) return 1;

  a %= base;

  if (k % 2 === 1) {
    // k 是奇数
    return (a * mypow(a, k - 1)) % base;
  } else {
    // k 是偶数
    const sub = mypow(a, k / 2);
    return (sub * sub) % base;
  }
}